python素数应用

#求一个数的比自己小的所有互质数的算法
#队列关系：a d N，a = (a d N) % N，由a和N求d
#类似环形队列：初始点a不影响计算，实则由N求d
N = 840#求一个数的所有因数
def get_factor(a):
 l = []
 for i in range(1,a 1): #输出1~(a-1)
  if (a % i) == 0:
   l.append(i)
 return l#判断2个数是否互质：公约(因)数只有1的两个数叫做互质数。
def is_coprime(a,b):
 a1 = get_factor(a)
 a1.remove(1)
 a2 = get_factor(b)
 a2.remove(1)
 for i in a1:
  for j in a2:
   if j == i:
    return 0
 return 1# x * D (x 属于1~N)除不尽 N
l1 = []
for d in range(1,N):
 for i in range(1,N):
  if ((i * d) % N) != 0: #在N-1次循环中除不够即为所需
   if i == (N - 1):
    l1.append(d) #全满足
   continue #继续执行下一轮判断
  else:
   break; #不到N就除尽不满足 
print(l1)l2 = []
for i in range(1,N):
 if is_coprime(i,N) == 1:
  l2.append(i)
print(l2)